indiscernible sequence?
Morley sequence?
Ramsey theorem?
Erdos-Rado theorem?
Ehrenfeucht-Fraïssé games (back-and-forth games)
Hrushovski construction?
generic predicate?
A definable set of an -theory in a first-order language is an equivalence class of formulas which evaluate the same way in every model of . (In the case that is empty, is just the class of -structures.)
Let be a first-order language and a theory in . Any formula , whose only free variables could be among , together with a model for evaluates to a truth value on each , hence it determines the subset of all such that . Two formulas with the same number of free variables are equivalent if for every model of . A definable set in is an equivalence class of formulas in under this relation. Consider the category of -structures and elementary embeddings and its full subcategory whose objects are the models of . We can also view a definable set for a theory as a functor which is of the form for some -formula .
By denote the set of all such that holds, i.e. is true for any choice of representative .
Given two definable sets in a definable function is a definable subset of the product sort such that is a function (we also write ) for every model of . Analogously a definable equivalence relation is a definable subset such that is an equivalence relation for every model of .
Proposition. Given a small category and two functors the natural transformations are in 1-1 correspondence with functors such that and such that is a functional relation.
Proof. If is an -indexed family with components viewed as functional relations , then the extension to a functor means
that there is a (automatically unique) dotted arrow
making the diagram commutative (once the existence of is known, the functoriality of comes by uniqueness of and the functoriality of which it restricts from). That means that for every should be sent to by , what is a restriction of , but by being functional relation this must be the same as , i.e. that . Q.E.D.
In other words, functoriality of is the same as being natural.
Corollary. Definable functions for (for ) are in 1-1 correspondence with natural transformations of definable sets as functors (resp. ).
For a fixed (multi-sorted, first-order) theory , definable sets and definable functions form a category . This category (or any equivalent category) is the syntactic category of the theory. Models of can be recovered as left exact functors . Notice that definable sets are functors from models to sets, and models are functors from definable sets to sets; just the latter are the “evaluation functionals” among all functors.
See also definable groupoid.
An -definable set is an intersection of definable sets.
We can also consider a relative version of a definable set (definability with parameters).
Given definable sets , a fixed model and a fixed set , we say that an element is definable over if there is and a -definable function such that . All elements definable over form the subset . A subset is definably closed if it is closed under definable functions. Given , there is the minimal definably closed subset such that , the definable closure of .
If we extend the language by the constants from we get a new language . The definable sets in language over are the definable sets in language over .
One can also study ind-objects and pro-objects in the category of definable sets and definable functions.
An important special case of a pro-definable set that shows up in model theory are type-definable sets, which are just infinite conjunctions of definable sets. (There is no restriction that the formulas representing these definable sets all sit inside a finite product of sorts.)
Moshe Kamensky, Ind- and Pro- definable sets, math.LO/0608163
Jan Holly, Definable operations on sets and elimination of imaginaries, Proc. Amer. Math. Soc. 117 (1993), no. 4, 1149–1157, MR93e:03052, doi, pdf
David Kazhdan, Lecture notes in model theory, pdf
D. Haskell, E. Hrushovski, H.D.Macpherson, Definable sets in algebraically closed valued fields: elimination of imaginaries, J. reine und angewandte Mathematik 597 (2006), MR2007i:03040, doi/CRELLE.2006.066)
Last revised on June 23, 2020 at 16:29:28. See the history of this page for a list of all contributions to it.